COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "lsp.pub[1,clt]" source_file
C00003 00003	.s IMPURE PROGRAMS AND UNCLEAN PROGRAMS
C00017 00004	.skip to column 1
C00018 ENDMK
C⊗;
.require "lsp.pub[1,clt]" source_file;
.PORTION MAINPORTION
.sname ← SSNAME ← NULL
.NEXT SECTION  
.NEXT SECTION
.NEXT SECTION

.s IMPURE PROGRAMS AND UNCLEAN PROGRAMS


	Pure clean LISP programs admit the elegant mathematical
characterization described and applied in Chapter 3.
Specifically, each recursively defined pure clean LISP function
can be translated into a functional equation and minimization
schema in a first order language, and the function and schema
can be used to prove that the program meets its extensional
specifications.

	In this chapter we shall describe some additional features of
practical LISP systems for which good mathematical characterizations
have not yet been found.  Every computation that can be done with
these features can be done in pure clean LISP, but nevertheless there
are good reasons for sometimes using these features.  We shall examine
the features themselves and also the criteria that determine when
they should be used in preference to pure clean LISP.


.ss "Sequential (Algol-like) programs."

	Sequential programs are impure (by definition),
but can be clean - provided
certain restrictions are observed.  The external notation for
sequential programs is adapted from that of Algol 60.  We allow
as a term an expression of the form

	%2program[<variable list>,<statement list>]%1,

where %2<variable list>%1 is a list of variables local to the
program, and %2<statement list>%1 is a list of the statements of
the program.  As in Algol 60, the statements are separated by
semicolons, and any statement may be preceded by a label followed
by a colon.

	The statements are of the following kinds:

	1. Assignment statements of the form

	%2<left hand side> ← <right hand side>%1,

where %2<left hand side>%1 is a variable, possibly subscripted, and
%2<right hand side>%1 is a LISP expression that can be evaluated.

	2. %3go to%1 statements of the form

	%3go to%2 a%1

where %2a%1 is a label or a conditional expression that evaluates to a
label.

	3. A conditional statement which has the form

	%2qif p1 qthen s1 qelse qif ... qelse qif pn qelse sn%1,

where the %2p%1's are propositional expressions having truth values,
and the %2s%1's are any statements.

	4. %3return%2 e%1

where %2e%1 is an arbitrary expression.  The effect of executing this
expression is to return from the program giving the program as a term
the value of the expression %2e%1.

	As an example, we might write %2reverse%1 as follows:

.nofill

	%2reverse u ← %3program%2[[v];
		v ← qNIL;
	a:	qif qn u qthen %3return%2 v;
		v ← qa u . v;
		u ← qd v;
		%3go to%1 a]%1.
.fill

	The internal form of the same program is

.nofill

	(DE REVERSE (U) (PROG (V)
		(SETQ V NIL)
		A
		(COND ((NULL U) (RETURN V)))
		(SETQ V (CONS (CAR U) V))
		(SETQ U (CDR U))
		(GO A)
	))
.fill

where the paragraphing is only for the reader's convenience.  Notice that
in internal form, labels are statements rather than attachments to
statements.

	Here are some ways we might write %2append%1:
.nofill

	%2u * v ← %3program%2[
		%3return%2 qif qn u qthen v qelse qa u . [qd u * v]]%1,

.fill
is just a trivial rewrite of the recursive definition.
.nofill

	%2u * v ← qprogram[w;
		qif qn u qthen qreturn v;
		w ← qa u . [qd u * v];
		qreturn w]%1

.fill
is almost as close to the pure LISP form.  If we want to replace the
recursion by a loop, we can write

.nofill
	%2u * v ← qprogram[w;
		w ← qNIL;
	a:	qif qn u qthen qgoto b;
		w ← qa u . w;
		u ← qd u;
		qgoto a;
	b:	qif qn w qthen qreturn v;
		v ← qa w . v;
		qw ← qd w;
		qgoto b]%1.

.fill
This corresponds to the recursive program
.nofill

	%2u * v ← app[u,v,qnil]

	app[u,v,w] ← qif qn u qthen [qif qn w qthen v qelse app[u,qa w . v,qd w]]
		qelse app[qd u,v,qa u . w]%1

.fill
which can save some storage if it is compiled or interpreted without
using the stack.

	We shall not treat the mathematics of sequential programs fully
at this point.  However, a sequential program that occurs as a term
can be replaced by a term involving only functional
programs provided the following conditions
are observed:

	1. All variables local to the program are initialized
before being used.
Of course, it could be taken as a convention that these variables
are initialized to qNIL when the program is entered.  Then it
wouldn't affect the correctenss of the translation to a functional
program if some of them weren't further initialized.

	2. All assignments are to variables local to the program.
This condition actually excludes the above examples which would have
to be rewritten with a local variable %2u1%1 initialized to the
value of the program variable %2u%1.

	A new function definition is made for each branch (i.e. conditional
%3go_to%1) in the
original program.  The argument of the function is a list whose elements
are values assigned to the local variables, i.e. the list has as
many elements as there are local variables.  The value of the function
is the value that will be %3return%1ed from the program given that the
local variables have the values given in the argument when the branch
is reached.  The %3program%1 expression itself is replaced by an
application of the function corresponding to the first branch encountered
in the program to the state vector whose components
have the values they will have the first time the branch is reached
written as functions of the external variables.

	As an example, consider the following expression that gives the
result of appending the list %2a%1 with the reversal of %2a*b%1:

	%2a * %3program%2[[u,v] u ← a * b; v ← qnil; loop: qif qn u
qthen qreturn v; v ← qa u . v; u ← qd u; qgo loop]%1.

This expression can be replaced by

	%2a * loop <u, qnil>%1

and the recursive definition

	%2loop z ← qif qn qa z qthen qad z qelse loop <qda z, qaa z . qad z>%1.

	When the program makes assignments to external variables, an
ambiguity arises.  Suppose we evaluate the expression

	%2<x, %3program%2[[] x ← qd x], x>%1.

when ⊗x has the value (A B).  If the arguments of the list are "executed"
in right to left order, the expression will have value ((A B) (B) (B)),
whereas if the execution is from right to left, the value will be
((B) (B) (A B)).  However, the mathematical semantics of expressions
don't prescribe any order of evaluation, and experience with ALGOL 60,
which prescribed left-to-right evaluation in order to give a definite
meaning to function procedures that alter external variables, has shown
that the quality of compiled code is greatly reduced by prescribing
a fixed order.


Exercises:

	1. Write a LISP predicate that will determine whether a PROG
in internal form satisfies the above conditions for replacement by
a functional term.

	2. Given that a PROG satisfies the conditions, write a LISP
functions to convert the PROG expression and give the a list of the
required auxiliary function definitions.

	The reason for discussing how to rewrite the sequential program
as a functional program is to apply the the theory of chapter 3 to
the sequential case.  The above conditions permit a purely local rewrite,
but it seems evident that if an outer sequential program containing
an inner one satisfies the initialization and local assignment (i.e.
no side-effect) conditions, then the program can be converted to functional
form even if it contains sequential subprograms that violate these
conditions provided that all assignments in the inner program are at
least local to the outer program.  The rules for doing this have not
been formulated as yet.

	There are three circumstances in which sequential programs are
preferred to functional programs:

	1. In some cases and for some people, it is easier to think
about how to go from the initial conditions step-by-step to the final
result than to think about how the final result can be obtained from
easier cases.  There seems to be a matter of taste to a substantial
extent, though the functional form seems to have clear conceptual
advantages for functions like %2append%1 and %2subst%1.

	2. When there are a large number of variables, it can turn
out that the necessary functions have an unwieldy number of arguments.

	3. When we are considering a program that interacts with
an environment instead of producing an answer, the sequential form
may be required, although this hasn't been proved.

Remarks:

	1. Besides (SETQ var exp), most LISPs allow (SET exp1 exp2),
where ⊗exp1 is evaluated to determine to what variable the assignment
is to be made.  If ⊗exp1 doesn't evaluate to a variable, an error
is signalled.

	2. LISP admits arrays
.skip to column 1
1. Sequential programs

2. Side effects

3. Property lists

4. Input and output

5. EXPRS, FEXPRS, LEXPRS, SUBRS, FSUBRS, LEXPRS